package 剑指offer;

public class Offer19_JZ52 {

    public static boolean match (String str, String pattern) {
        return true;
    }

    public static boolean dp(String str, String pattern, int i, int j, boolean[][] mathced) {
        if (j == pattern.length()-1) {
            return i == str.length()-1;
        }
        boolean first = i<str.length() && (str.charAt(i)==pattern.charAt(j) || pattern.charAt(j)=='.');
        if (j < pattern.length()-2 && pattern.charAt(j+1) == '*') {
            mathced[i+1][j+1] = dp(str, pattern, i, j+2, mathced) || (first && dp(str, pattern, i+1, j, mathced));
        } else {
            mathced[i+1][j+1] = first && dp(str, pattern, i+1, j+1, mathced);
        }
        return mathced[str.length()+1][pattern.length()+1];
    }
}
